<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(B卷,200分)- 目录删除（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>某文件系统中有 N 个目录&#xff0c;每个目录都有一个独一无二的 ID。</p> 
<p>每个目录只有一个父目录&#xff0c;但每个父目录下可以有零个或者多个子目录&#xff0c;目录结构呈树状结构。</p> 
<p>假设&#xff0c;根目录的 ID 为 0&#xff0c;且根目录没有父目录&#xff0c;其他所有目录的 ID 用唯一的正整数表示&#xff0c;并统一编号。</p> 
<p>现给定目录 ID 和其父目录 ID 的对应父子关系表[子目录 ID&#xff0c;父目录 ID]&#xff0c;以及一个待删除的目录 ID&#xff0c;请计算并返回一个 ID 序列&#xff0c;表示因为删除指定目录后剩下的所有目录&#xff0c;返回的ID序列以递增序输出。</p> 
<p><strong>注意</strong></p> 
<p>1、被删除的目录或文件编号一定在输入的 ID 序列中&#xff1b;</p> 
<p>2、当一个目录删除时&#xff0c;它所有的子目录都会被删除。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>输入的第一行为父子关系表的长度 m&#xff1b;</p> 
<p>接下来的 m 行为 m 个父子关系对&#xff1b;</p> 
<p>最后一行为待删除的 ID。</p> 
<p>序列中的元素以空格分割&#xff0c;参见样例。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>输出一个序列&#xff0c;表示因为删除指定目录后&#xff0c;剩余的目录 ID。</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">5<br /> 8 6<br /> 10 8<br /> 6 0<br /> 20 8<br /> 2 6<br /> 8</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">2 6</td></tr><tr><td style="width:86px;">说明</td><td style="text-align:center;width:412px;"><img alt="" src="https://img-blog.csdnimg.cn/f0ff7323009e47699c2ac8fac35c14a3.png" /></td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题咋看上去是让模拟N叉树结构&#xff0c;然后做节点删除操作&#xff0c;最后遍历N叉树。</p> 
<p>但是这样的话思考的话&#xff0c;就太复杂了。</p> 
<p>本题其实并不需要删除节点&#xff0c;也不需要遍历N叉树&#xff0c;我们可以在模拟N叉树的过程中&#xff0c;就统计节点&#xff0c;并排除要删除的节点的插入。</p> 
<p>我首先&#xff0c;统计了所有父节点下的子节点&#xff0c;比如</p> 
<p>8 6<br /> 10 8<br /> 6 0<br /> 20 8<br /> 2 6</p> 
<p>可以统计为&#xff1a;</p> 
<pre><code class="language-javascript">tree &#xff1a; {
  0: [6]
  6: [8, 2],
  8: [10, 20]
  2: []
}</code></pre> 
<p>然后从根节点0开始遍历N叉树</p> 
<pre><code class="language-javascript">let children &#61; tree[0]
for(let i&#61;0; i&lt;children.length; i&#43;&#43;) {
  if(children[i] !&#61;&#61; remove) {
    // 记录树节点
    // 递归处理children[i]&#xff0c;即将children[i]当成父节点继续遍历查找其子节点&#xff0c;重复上面逻辑
  }
}</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int m &#61; sc.nextInt();

    int[][] relations &#61; new int[m][2];
    for (int i &#61; 0; i &lt; m; i&#43;&#43;) {
      relations[i][0] &#61; sc.nextInt();
      relations[i][1] &#61; sc.nextInt();
    }

    int del &#61; sc.nextInt();

    System.out.println(getResult(m, relations, del));
  }

  public static String getResult(int m, int[][] relations, int del) {
    HashMap&lt;Integer, ArrayList&lt;Integer&gt;&gt; tree &#61; new HashMap&lt;&gt;();

    for (int[] relation : relations) {
      int child &#61; relation[0];
      int father &#61; relation[1];
      tree.putIfAbsent(father, new ArrayList&lt;&gt;());
      tree.get(father).add(child);
    }

    if (del &#61;&#61; 0) {
      return &#34;&#34;;
    }

    ArrayList&lt;Integer&gt; res &#61; new ArrayList&lt;&gt;();
    dfs(tree, 0, del, res);

    res.sort((a, b) -&gt; a - b);
    StringJoiner sj &#61; new StringJoiner(&#34; &#34;);
    for (Integer v : res) {
      sj.add(v &#43; &#34;&#34;);
    }
    return sj.toString();
  }

  public static void dfs(
      HashMap&lt;Integer, ArrayList&lt;Integer&gt;&gt; tree, int node, int del, ArrayList&lt;Integer&gt; res) {
    if (tree.containsKey(node)) {
      ArrayList&lt;Integer&gt; children &#61; tree.get(node);
      for (Integer child : children) {
        if (child !&#61; del) {
          res.add(child);
          dfs(tree, child, del, res);
        }
      }
    }
  }
}
</code></pre> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JS算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
let m;
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 1) {
    m &#61; parseInt(lines[0]);
  }

  if (m &amp;&amp; lines.length &#61;&#61;&#61; m &#43; 2) {
    lines.shift();
    const del &#61; parseInt(lines.pop());
    const arr &#61; lines.map((line) &#61;&gt; line.split(&#34; &#34;).map(Number));

    console.log(getRemainTreeEle(arr, del));
    lines.length &#61; 0;
  }
});

function getRemainTreeEle(arr, del) {
  let tree &#61; {};

  for (let i &#61; 0; i &lt; arr.length; i&#43;&#43;) {
    let [child, father] &#61; arr[i];
    tree[father] ? tree[father].push(child) : (tree[father] &#61; [child]);
  }

  if (del &#61;&#61;&#61; 0) return &#34;&#34;;

  const res &#61; [];
  dfs(tree, 0, del, res);

  return res.sort((a, b) &#61;&gt; a - b).join(&#34; &#34;);
}

function dfs(tree, node, del, res) {
  const children &#61; tree[node];
  if (children)
    for (let i &#61; 0; i &lt; children.length; i&#43;&#43;) {
      if (children[i] !&#61;&#61; del) {
        res.push(children[i]);
        dfs(tree, children[i], del, res);
      }
    }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
m &#61; int(input())
relations &#61; [list(map(int, input().split())) for _ in range(m)]
remove &#61; int(input())


def dfs(tree, node, remove, res):
    if tree.get(node) is not None:
        children &#61; tree[node]
        for child in children:
            if child !&#61; remove:
                res.append(child)
                dfs(tree, child, remove, res)


# 算法入口
def getResult():
    tree &#61; {}

    for child, father in relations:
        if tree.get(father) is None:
            tree[father] &#61; []
        tree[father].append(child)

    if remove &#61;&#61; 0:
        return &#34;&#34;

    res &#61; []
    dfs(tree, 0, remove, res)

    res.sort()
    return &#34; &#34;.join(map(str, res))


# 调用算法
print(getResult())
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>